#include <iostream>
using namespace std;

template<class K ,class T>
class HASHTABLE
{
public:
    HASHTABLE(int &capacity);
    ~HASHTABLE();
    int hash(const K &thekey);
    int search(const K &thekey);
    int size();
    pair<K,T>* find(const K &thekey);
    void insert(const pair <K,T> &thepair);
    void earse(const K &thekey);
    void display();
private:
    pair<K,T>** table;
    int dsize;
    int divisor;
};

template <class K,class T>
HASHTABLE<K,T>::HASHTABLE(int &capacity)
{
    divisor=capacity;
    table=new pair<K,T>* [divisor];
    for(int i=0;i<divisor;i++)
        table[i]=NULL;
    dsize=0;
};


template <class K,class T>
HASHTABLE<K,T>::~HASHTABLE()
{
    delete [] table;
};

template <class K,class T>
int HASHTABLE<K,T>::hash(const K &thekey)
{
    return (int)thekey;
};

template <class K, class T>
int HASHTABLE<K,T>::search(const K &thekey)
{
    int i=hash(thekey)%divisor;
    int j=i;
    do
    {
        if(table[j]==NULL||table[j]->first==thekey)
        {
            return j;
        }
        else
        {
            cout<<"cant find the element which key is"<<endl;
            return NULL;}
        j=(j+1)%divisor;
    }while(j!=i);
};

template <class K, class T>
pair<K,T>* HASHTABLE<K,T>::find(const K &thekey)
{
    int b=search(thekey);
    if(table[b]==NULL||table[b]->first!=thekey)
    {
        cout<<"can't find thekey"<<endl;
        return NULL;
    }
        else return table[b];
};

template<class K,class T>
void HASHTABLE<K,T>::insert(const pair<K,T> &thepair)
{
    int i=search(thepair.first);
    if(table[i]==NULL)
    {
        table[i]=new pair<K,T>(thepair);
        dsize++;
    }
    else if(table[i]->first==thepair.first)
    {
        cout<<"replace the "<<i<<"postion element"<<endl;
        table[i]->second=thepair.second;
    }
    else
    {
        cout<<"error the postion have a different pair"<<endl;
    }
};

template<class K,class T>
void HASHTABLE<K,T>::earse(const K &thekey)
{
    int i=search(thekey);
    if(table[i]->first==thekey)
    {
        table[i]=NULL; // FIXME: 内存泄露！`insert`的时候分配内存了，这里需要释放。同理，析构函数也需要释放
        dsize--;
    }
    else cout<<"there is not the element"<<endl;
};

template<class K,class T>
void HASHTABLE<K,T>::display()
{

    for(int i=0;i<divisor;i++)
    {
        if(table[i]!=NULL)
        {
            cout<<table[i]->first<<" "<<table[i]->second<<endl;
        }
        else
        {
            cout<<"NULL"<<" ";
        }
    }
};

template<class K,class T>
int HASHTABLE<K,T>::size()
{
    return dsize;
};

int main()
{
    int n=8;
    HASHTABLE<int,int> a(n);
    for(int i=4;i<12;i++)
    {
        pair<int,int> b;
        b.first=i;
        b.second=i*2;
        a.insert(b);
    }
    a.display();
    cout<<a.size()<<endl;

    a.earse(8);
    a.display();
    cout<<a.size()<<endl;
    pair<int,int>* b;
    b=a.find(6);
    cout<<b->first<<" "<<b->second<<endl;

    system("pause");
    return 0;
}

// FIXME:
//  1. 写完之后，保证逻辑、执行没有错误之后，需要检查一下内存分配、释放是否配对了。
//  2. 建议你类的名字写成 `HasTable`

